//
// Created by Lenovo on 2024/2/29.
//
#include<bits/stdc++.h>
using namespace std;
//飞地的数量,即找被海洋包围的陆地单元格的数量
class Solution {
public:

    int m,n;
    int res=0,cnt=0;            //res为最终返回值，cnt为当前陆地的单元格数量
    bool st[501][501];          //st[x][y]表示该位置是否走过
    bool flag= true;           //flag用于表示该片陆地有无被海洋包围
    int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

    void dfs(int x,int y,vector<vector<int>>& grid){
        if(x==0 || x==m-1 || y==0 || y==n-1){       //到达边界，说明没有被海洋包围
            flag= false;
        }
        for(int i=0;i<4;i++){
            int nextX=x+go[i][0];
            int nextY=y+go[i][1];
            if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && !st[nextX][nextY] && grid[nextX][nextY]==1){
                st[nextX][nextY]=true;
                cnt++;
                dfs(nextX,nextY,grid);
            }
        }
    }

    int numEnclaves(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!st[i][j] && grid[i][j]==1){
                    flag=true;                  //默认为被海洋包围
                    st[i][j]= true;
                    cnt++;
                    dfs(i,j,grid);
                    if(flag) res+=cnt;          //如果被海洋包围就将该陆地数量计入结果
                    cnt=0;
                }
            }
        }
        return res;
    }
};